The present invention relates generally to image recognition, and more particularly to image recognition via use of the Hough transform.
The Hough transform represents a known technique which has achieved widespread use in image recognition systems. For example, U.S. Pat. No. 4,868,752 (Fujii et al) discloses an automatic working vehicle control system having a boundary detecting system which employs the Hough transform. As described therein, a portion of a working area forward of the vehicle is photographed and a variable density image is produced according to edge data derived from the brightness level of image pixels.
Transition points in the image where dense portions of the image change into light portions are identified to detect a boundary line. The boundary line distinguishes a dark, untreated area (e.g., if the vehicle is a lawn mower, the untreated area corresponds to uncut lawn) and a treated area (e.g., cut lawn) along which the vehicle is to be guided. The Hough transform is employed to avoid false detection of noise (due, for example, to bright spots which occur in the untreated area and dark spots which occur in the treated area) as the boundary along which the vehicle is to be guided.
More particularly, as shown in FIG. 13 of U.S. Pat. No. 4,868,752, the Hough transform can detect a straight line representing an image boundary despite the presence of surrounding noise in the image. Basically, the Hough transform acts upon pixel values of a digitized image. The Hough transform assigns a locus curve to the (x,y) coordinates of each pixel value having an intensity which corresponds to that of a boundary line condition. The locus curve for each of these pixels corresponds to a polar coordinate transformation of the (x,y) coordinates for each such pixel. A straight line used to represent the boundary line in the image is then obtained by finding the polar coordinates of a point where the curves representing the loci concentrate.
Although many forms of the Hough transform have been used in a variety of systems, this transformation is most often implemented in software and involves significant processing time. More than one minute is typically required to process each frame of image data using a software implementation of the Hough transform. Further, even where specialized hardware is used to enhance the processing speed, real time processing at a typical frame rate of image data acquisition (i.e., 30 frames of image data per second) has not been achieved.
For example, the document entitled "A Real-Time Processor for the Hough Transform", IEEE Transactions on Pattern Analysis and Machine Intelligence, Hanahara, Keishi et al., Vol. 10, No. 1, January 1988 relates to dedicated straight line detection hardware which uses the Hough transform. More specifically, an experimental model which exploits parallel processing and pipelining techniques is described. For a gray-scale picture with 1024 feature points, total processing time for an image using standard TTL circuits is described as being 0.79 seconds, not including time for clearing a histogram memory used during processing.
In another document entitled "A Monolithic Hough Transform Processor Based on Restructurable VLSI", IEEE Transactions On Pattern Analysis and Machine Intelligence, Rhodes, F. Matthew et al., Vol. 10, No. 1, January 1988, an implementation of a Hough transform processor using a wafer-scale integration technology, restructurable VLSI, is described. A basic implementation for a typical line extraction is described as being performed using a traditional Hough transform implementation.
In European Patent Application No. A2-361,914 to Nakayama et al., a specialized implementation of the Hough transform is described for judging a contour of a road by processing data of an image taken of the road by a camera. Processing is apparently performed using known Hough transform techniques for extracting straight lines in first and second regions of a digitized image. However, no specific hardware which would permit real-time implementation of Hough processing for the potentially numerous edges present in either or both of the first and second regions shown, for example, in FIGS. 16 and 17 is disclosed.
Thus, while efforts have been made to enhance the speed of image analysis processing using the Hough transform, versatile implementations having a potential processing speed which can exceed that of typical digital image data acquisition are not presently available. Accordingly, it would be desirable to provide an image processor which includes a versatile, real time implementation of the Hough transform.